package marek.ai;

/**
 * By Marek Jankowski
 * jankowski.marek@gmail.com
 * Any comments or questions are welcome.
 * 
 * License: GNU GPL v3: http://www.gnu.org/licenses/gpl.html
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Simple implementation of a Hopefield network. With implicit threshold = 0.
 * 
 * I created this class to study Hopefield networks. It's simple and low level
 * so should give good understanding of actual implementation.
 * 
 * @author marek
 * 
 */

public class Hopefield {
	private final static int PATTERN_WIDTH = 10;
	private final static int PATTERN_HEIGHT = 10;
	private final static int UNCHANGED_STATE_THRESHOLD = 300;
	
	private List<Neuron> neurons = new ArrayList<Neuron>(PATTERN_WIDTH
			* PATTERN_HEIGHT);
	private List<Synapse> synapses = new ArrayList<Synapse>();
	public final static String[] PATTERNS = {
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " +
		"    XX    " ,	

		"XXXXXXXXXX" +
		"        XX" +
		"        XX" +
		"        XX" +
		"        XX" +
		"XXXXXXXXXX" +
		"XX        " +
		"XX        " +
		"XX        " +
		"XXXXXXXXXX" ,	

		"XXXXXXXXXX" +
		"        XX" +
		"        XX" +
		"        XX" +
		"  XXXXXXXX" +
		"  XXXXXXXX" +
		"        XX" +
		"        XX" +
		"        XX" +
		"XXXXXXXXXX" ,	

		"XX   XX   " +
		"XX   XX   " +
		"XX   XX   " +
		"XX   XX   " +
		"XX   XX   " +
		"XXXXXXXXXX" +
		"     XX   " +
		"     XX   " +
		"     XX   " +
		"     XX   " 	
	};

	private class Neuron {
		private List<Neuron> connections = new ArrayList<Neuron>();
		private List<Synapse> connectingSynapses = new ArrayList<Synapse>();
		private int id;
		private int state; // either -1 or 1

		private Neuron() {
			id = neurons.size();
		}

		public boolean equals(Object o) {
			if (!(o instanceof Neuron)) {
				return false;
			}
			Neuron n = (Neuron) o;
			return n.getId() == this.getId();
		}

		public int getState() {
			return state;
		}

		public void setState(int state) {
			this.state = state;
		}

		public int getId() {
			return id;
		}

		public boolean isConnected(Neuron n) {
			return connections.contains(n);
		}

		public Synapse connectTo(Neuron n) {
			Synapse s = new Synapse();
			s.setFrom(this);
			s.setTo(n);
			this.connections.add(n);
			n.connections.add(this);
			this.connectingSynapses.add(s);
			n.connectingSynapses.add(s);
			return s;
		}

		public Synapse getSynapseTo(Neuron n) {
			for (Iterator iterator = connectingSynapses.iterator(); iterator
					.hasNext();) {
				Synapse s = (Synapse) iterator.next();
				if (s.getTo().equals(n) || s.getFrom().equals(n)) {
					return s;
				}
			}
			throw new RuntimeException("Could not find synapse from neuron "
					+ getId() + " to neuron " + n.getId());
		}

		/* 
		 * Runs activation function (0 threshold) and returns boolean value based on state change
		 */
		public boolean activate() {
			int prevState = getState();
			double sum = 0;
			for (Neuron n : neurons) {
				if (n.equals(this)) {
					continue;
				}
				Synapse s = getSynapseTo(n);
				sum += s.getWeight() * n.getState();
			}
			if (sum > 0) {
				setState(1);
			} else {
				setState(-1);
			}
			return prevState != getState();
		}
	}

	private class Synapse {
		public double getWeight() {
			return weight;
		}

		public void setWeight(double weight) {
			this.weight = weight;
		}

		public Neuron getFrom() {
			return from;
		}

		public void setFrom(Neuron from) {
			this.from = from;
		}

		public Neuron getTo() {
			return to;
		}

		public void setTo(Neuron to) {
			this.to = to;
		}

		private double weight = 0;
		private Neuron from;
		private Neuron to;
	}

	public void train() {
		System.out.println("Training patterns...");
		// each synapse weight = (Summation of all qi*qj pixels for all training vectors) * 1/number of training vectors
		for (int i = 0; i < PATTERNS.length; i++) {
			System.out.println("Training pattern " + i + "...");
			int[] patternData = convertPatternData(PATTERNS[i]);
			setState(patternData);
			for (Synapse s : synapses) {
				Neuron ni = s.getFrom();
				Neuron nj = s.getTo();
				double weight = s.getWeight();
				weight += ni.getState() * nj.getState();
				s.setWeight(weight);
			}
		}
		for (Synapse s : synapses) {
			double weight = s.getWeight();
			weight = weight * 1 / neurons.size();
			s.setWeight(weight);
		}
		System.out.println("Done training " + PATTERNS.length + " patterns.");
	}

	private int[] convertPatternData(String pattern) {
		int[] patternData = new int[pattern.length()];
		for (int i = 0; i < patternData.length; i++) {
			if (pattern.charAt(i) == 'X') {
				patternData[i] = 1;
			} else {
				patternData[i] = -1;
			}

		}
		return patternData;
	}

	private String convertFromData(int[] data) {
		StringBuffer sb = new StringBuffer(data.length + (data.length / 10));
		for (int i = 0; i < data.length; i++) {
			if (i % 10 == 0) {
				sb.append("\r\n");
			}
			if (data[i] > 0) {
				sb.append("X");
			} else {
				sb.append(" ");
			}
		}
		return sb.toString();
	}

	public String evaluate(String pattern) {
		System.out.println("Looking for:\r\n"
				+ convertFromData(convertPatternData(pattern)));
		int[] patternData = convertPatternData(pattern);
		setState(patternData);
		System.out.println("Stablizing network...");
		runUntilStable();
		return convertFromData(getState());
	}

	private void runUntilStable() {
		boolean stable = false;
		int count = 0;
		int noChangeCounter = 0;
		double prevEnergy = computeEnergy();
		double currentEnergy = prevEnergy;
		Neuron prevNeuron = null;
		while (!stable) {
			Neuron n = getRandomNeuron(prevNeuron); 
			boolean stateChanged = n.activate();
			System.out.println("Ran epoch #" + count++ + " on neuron " + n.getId() + ". State changed? " + stateChanged);
			if (stateChanged) {
				currentEnergy = computeEnergy();
				prevEnergy = currentEnergy;
				System.out.println("Energy state: " + currentEnergy);
				noChangeCounter = 0;
			} else if (prevEnergy == currentEnergy && noChangeCounter++ > UNCHANGED_STATE_THRESHOLD) {
				stable = true;
			}
			System.out.println(convertFromData(getState()));
		}
	}

	private Neuron getRandomNeuron(Neuron n) {
		int index = (int) (Math.random() * (neurons.size() + 1)) - 1;
		if (index < 0) {
			index = 0;
		}
		if (n != null && neurons.get(index).equals(n)) {
			return getRandomNeuron(n);
		}
		return neurons.get(index);
	}

	private void setState(int[] patternData) {
		// Set each patternData in a neuron value
		for (int i = 0; i < patternData.length; i++) {
			Neuron n = neurons.get(i);
			n.setState(patternData[i]);
		}
	}

	private int[] getState() {
		int[] state = new int[neurons.size()];
		int i = 0;
		for (Iterator iterator = neurons.iterator(); iterator.hasNext();) {
			Neuron n = (Neuron) iterator.next();
			state[i++] = n.getState();
		}
		return state;
	}

	private double computeEnergy() {
		double sum = 0.0;
		for (Synapse s : synapses) {
			Neuron ni = s.getFrom();
			Neuron nj = s.getTo();
			sum += s.getWeight() * ni.getState() * nj.getState();
		}
		sum *= -0.5;
		return sum;
	}

	public void generateNetwork() {
		System.out.println("Generating network...");
		neurons.clear();
		synapses.clear();
		// Create all neurons
		for (int i = 0; i < PATTERN_WIDTH * PATTERN_HEIGHT; i++) {
			Neuron n = new Neuron();
			neurons.add(n);
		}
		System.out.println("Generated " + neurons.size() + " neurons.");

		// Link all neurons: symmetrically, no self connection
		for (Neuron n1 : neurons) {
			for (Neuron n2 : neurons) {
				if (!n1.equals(n2) && !n1.isConnected(n2)) {
					Synapse s = n1.connectTo(n2);
					synapses.add(s);
				}
			}
		}

		System.out.println("Generated " + synapses.size()
				+ " weighted synapses.");
	}

	public static void main(String[] args) {
		Hopefield h = new Hopefield();
		h.generateNetwork();
		h.train();
		String test = 
			"XXX XXXXXX" +
			"        XX" +
			"        XX" +
			"        XX" +
			"        XX" +
			"XXXXXXXXXX" +
			" XXX      " +
			" XXX      " +
			" XXX      " +
			"X XXXXXXXX";	
		System.out.println("Found following p:\r\n: " + h.evaluate(test));
	}
}
